\input{euler.tex}

\begin{document}

\problem[301]{Nim}

\emph{Nim} is a game played with heaps of stones, where two players take it in turn to remove any number of stones from any heap until no stones remain.

The three-heap normal-play version of Nim works as follows:

1. At the start of the game there are three heaps of stones.

2. On his turn the player removes any positive number of stones from any single heap.

3. The first player unable to move (because no stones remain) loses.

If $(n_1,n_2,n_3)$ indicates a Nim position consisting of heaps of size $n_1$, $n_2$ and $n_3$, then there is a simple function $X(n_1,n_2,n_3)$ that returns zero if, with perfect strategy, the player about to move will eventually lose, or non-zero if, with perfect strategy, the player about to move will eventually win.

For how many positive integers $n \le 2^{30}$ is $X(n,2n,3n) = 0$?

\solution

It can be shown that $X(n_1,n_2,n_3) = n_1 \oplus n_2 \oplus n_3$ where $\oplus$ is the XOR operator. So the problem is to find out how many $1 \le n \le 2^{30}$ satisfy $X(n) = n \oplus 2n \oplus 3n = 0$.

Let's examine the right-most (least-significant) few bits of $n$. If the right-most bit is zero, i.e. $n$ is even, then it can be shown that $X(n)=0 \Leftrightarrow X(n/2)=0$, because we can just rip off the right-most bit of $n$ without changing the zero-ness of $X$.

If the right-most bit of $n$ is 1, we examine the right-most three bits:
\begin{center}
\begin{tabular}{c | r r r r}
\hline
$n$       & 001 & 011 & 101 & 111 \\
$2n$      & 010 & 110 & 010 & 110 \\
$3n$      & 011 & 001 & 111 & 101 \\
\hline
$\oplus$  & 000 & 100 & 000 & 100 \\
\hline
\end{tabular}
\end{center}
It can be seen that in order for $X(n)$ to be zero, the last two bits must be 01. In addition, when the last two bits are 01, $2n$ and $3n$ do not carry to higher bits. Hence, the bits to the left of the last two bits can be examined independently.

In summary, to determine whether $X(n)=0$, we go through the bits of $n$ from right to left. We require either the last bit be 0, or the last two bits be 01.

Let $F(k)$ denote the number of $k$-bit integers $0 \le n < 2^k$ such that $X(n)=0$. Then we have
\[
F(k)=F(k-1)+F(k-2) ,
\]
with $F(1)=2$ and $F(2)=3$. This coincides with the Fibonacci sequence!

Finally, we note that $F(k)$ is also the answer to this problem by replacing $n = 0$ with $n = 2^k$.

\complexity

Time complexity: $\BigO(k)$.

Space complexity: $\BigO(1)$.

\answer

2178309

\reference

http://en.wikipedia.org/wiki/Nim

\end{document} 
